Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret. When a cryptographic algorithm is designed, it is usually assumed that a potential attacker has access to only the public values. Without the secret information it is computationally infeasible to break the scheme or the algorithm. Once an attacker is in possession of a piece of secret information they may be able to forge the signature of the victim and also decrypt secret messages intended for the victim. Thus it is of paramount importance to maintain the secrecy and integrity of the secret information in the system. The secret information is generally stored within a secure boundary in the memory space of the cryptographic processor, making it difficult for an attacker to gain direct access to the secret information. Manufacturers incorporate various types of tamper-proof hardware to prevent illicit access to the secret information. In order to decide how much tamper proofing to implement in the cryptographic system, the designers must consider the resources available to a potential attacker and the value of the information being protected. The magnitude of these resources is used to determine how much physical security to place within the device to thwart attackers who attempt to gain direct access to the secure memory. Tamper-proof devices can help prevent an attacker who is unwilling or unable to spend large amounts of time and money from gaining direct access to the secret information in the cryptographic system. Typically, the amount of work that is required to defeat tamper proof hardware exceeds the value of the information being protected.
However, a new class of attacks has been developed on cryptographic systems that are relatively easy and inexpensive to mount in practice since they ignore the tamper-proof hardware. Recent attacks on cryptographic systems have shown that devices with secure memory may leak information that depends on the secret information, for example in the power usage of a processor computing with private information. Such attacks take advantage of information provided by an insecure channel in the device by using the channel in a method not anticipated by its designers, and so render redundant any tamper proofing in the device. Such insecure channels can be the power supply, electromagnetic radiation, or the time taken to perform operations. At particular risk are portable cryptographic tokens, including smart cards, pagers, personal digital assistants, and the like. Smart cards are especially vulnerable since they rely on an external power supply, whose output may be monitored non-intrusively. Access to the power supply is required for proper functioning of the device and so is not usually prevented with tamper-proof hardware.
Further, constrained devices tend not to have large amounts of electromagnetic shielding. Since the device is self-contained and dedicated, the power consumption and electromagnetic radiation of the smart card may be monitored as the various cryptographic algorithms are executed. Thus in a constrained environment, such as a smart card, it may be possible for an attacker to monitor an unsecured channel that leaks secret information. Such monitoring may yield additional information that is intended to be secret which, when exposed, can significantly weaken the security of a cryptographic system.
In response to the existence of such unsecured channels, manufacturers have attempted to minimize the leakage of information from cryptographic devices. However, certain channels leak information due to their physical characteristics and so it is difficult to completely eliminate leakage. A determined attacker may be able to glean information by collecting a very large number of samples and applying sophisticated statistical techniques. In addition, there are severe restrictions on what can be done in hardware on portable cryptographic tokens that are constrained in terms of power consumption and size. As a result, cryptographic tokens are particularly vulnerable to these types of attacks using unsecured channels.
The more recent attacks using the power supply that can be performed on these particularly vulnerable devices are simple power analysis, differential power analysis, higher order differential power analysis, and other related techniques. These technically sophisticated and extremely powerful analysis tools may be used by an attacker to extract secret keys from cryptographic devices. It has been shown that these attacks can be mounted quickly and inexpensively, and may be implemented using readily available hardware.
The amount of time required for these attacks depends on the type of attack and varies somewhat by device. For example it has been shown that simple power analysis (SPA) typically takes a few seconds per card, while differential power analysis (DPA) can take several hours. In order to perform SPA, the attacker usually only needs to monitor one cryptographic operation. To perform DPA, many operations must be observed. In one method used, in order to monitor the operations, a small resistor is connected in series to smart card's power supply and the voltage across the resistor is measured. The current used can be found by a simple computation based on the voltage and the resistance. A plot of current against time is called a power trace and shows the amount of current drawn by the processor during a cryptographic operation. Since cryptographic algorithms tend to perform different operations having different power requirements depending on the value of the secret key, there is a correlation between the value of the secret key and the power consumption of the device.
Laborious but careful analysis of end-to-end power traces can determine the fundamental operation performed by the algorithm based on each bit of a secret key and thus, be analyzed to find the entire secret key, compromising the system. DPA primarily uses statistical analysis and error correction techniques to extract information that may be correlated to secret keys, while the SPA attacks use primarily visual inspection to identify relevant power fluctuations. In SPA, a power trace is analyzed for any discernible features corresponding to bits of the secret key. The amount of power consumed varies depending on the executed microprocessor instructions. For example, in a typical “square-and-multiply” algorithm for exponentiation, a bit 1 in the exponent will cause the program to perform both squaring and multiply operations, while a bit 0 will cause the multiply operation to be skipped. An attacker may be able to read off the bits of a secret exponent by detecting whether the multiply operation is performed at different bit positions.
A DPA attack attempts to detect more subtle features from the power traces and is more difficult to prevent. To launch a DPA attack, a number of digital signatures are generated and the corresponding power traces are collected. The power trace may be regarded as composed of two distinct parts, namely signal and noise. The patterns that correspond to private key operations tend to remain more or less constant throughout all power traces. These patterns may be regarded as the signal. The other parts of the computation, which correspond to changing data, result in differing patterns in each power trace. These patterns can be regarded as the noise. Statistical analysis can be performed on all the power traces to separate the signal from the noise. The secret value is then derived using the identified signal.
Various techniques for preventing these power analysis attacks have been attempted to date. Manufacturers of smart cards and smart card processors have introduced random wait states and address scrambling. Smart card algorithms avoid performing significantly different operations depending on the value of a secret key and also avoid conditional jump instructions. Hardware solutions include providing well-filtered power supplies and physical shielding of processor elements or the addition of noise unrelated to secrets. However, the vulnerabilities to DPA result from transistor and circuit electrical behaviors that propagate to exposed logic gates, microprocessor operation, and ultimately the software implementations. Cryptographic algorithms to date have been designed with the assumption that there is no leakage of secret information, however with the advent of successful power analysis attacks, it is no longer prudent to assume that a cryptographic device which will leak no secret information can be manufactured. Information stored in constrained environments is particularly difficult to protect against leakage through an unsecured channel during cryptographic operations.
Accordingly, there is a need for a system for reducing the risk of a successful power analysis attack and which is particularly applicable to current hardware environments.